package class03;

public class Code02_Manacher {

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	public static int maxLcpsLength(String str) {
		if (str == null || str.length() == 0) {
			return 0;
		}
		char[] charArr = manacherString(str); // 1221 -> #1#2#2#1#
		int[] pArr = new int[charArr.length]; // 回文半径数组
		int C = -1; // 中心
		int R = -1; // 回文右边界的再往右一个位置 最大的有效区是R-1位置 （小改进）
		int max = Integer.MIN_VALUE; // 扩出来的最大值
		for (int i = 0; i != charArr.length; i++) {

			// i至少不用验的回文半径先给pArr
			// 包括情况（1），i在R外，pArr[i] = 1。 i指向第一个字符，此时回文半径是1，也就是他自己
			// 还包括情况（2），i在R外，的 ① ② 和 ③
			pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1; // 2*C-i 是 i' 的位置

			// 虽然只有（1）和（2）的③需要外扩，但是为了代码短这么写。
			// （2）的①和②是不需要扩的，在这里面扩一次也会失败
			// 复杂度没有改变
			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
				if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) // 左右扩散
					pArr[i]++;
				else {
					break;
				}
			}
			// 看一下有没有更往右，有的话更新R和C
			if (i + pArr[i] > R) {
				R = i + pArr[i];
				C = i;
			}
			max = Math.max(max, pArr[i]);
		}

		// 处理串的回文半径长度 - 1 = 原始串长度
		return max - 1;
	}

	public static void main(String[] args) {
		String str1 = "abc1234321ab";
		System.out.println(maxLcpsLength(str1));
	}

}
